package Algorithms.recall;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.stream.Collectors;

/*
 * @Author 罗俊
 * @date 2020/10/29 - 7:59 上午
 *
 */
public class Recall {

    private static final int[][] HorseChessBroad = new int[10][10];

    public static void main(String[] args) {

        List<HorseChessLocation> path = new LinkedList<>();

        // 起点
        HorseChessLocation startLocation = new HorseChessLocation(4, 1);
        // 把起点记录在棋盘上
        HorseChessBroad[startLocation.getColumn()][startLocation.getRow()] = -1;
        // 把起点添加到走过的记录中
        path.add(startLocation);

        List<StepRecord> stepRecords = new ArrayList<>();

        go(startLocation/*, path*/, stepRecords, 0, null);
    }






    public static void go(HorseChessLocation horseChessLocation,
            /*List<HorseChessLocation> path,*/ List<StepRecord> stepRecords,
                          Integer stepCount,
                          Integer assignStepCount) {
        List<HorseChessLocation> availableNextStep = null;

        if (horseChessLocation != null) {
            // 如果棋（horseChessLocation）的当前位置为 null，就说明是要回溯，可用的步数已经在 stepRecords 修改好了，直接获取就行
            availableNextStep = availableNextStep(horseChessLocation);
        } else {
            // 回溯，从 stepRecords 中获取 可用的步骤
            availableNextStep = stepRecords.get(stepCount).getAvailableNextStep();

        }


        System.out.println("下一步可以走：" + availableNextStep + "已经走了" + stepCount + "步");

        StepRecord stepRecord = new StepRecord();

        stepRecord.setAvailableNextStep(availableNextStep);

        if (availableNextStep.size() > 0) {

            HorseChessLocation nextStep = availableNextStep.get(0);

            stepRecord.setActuallyNextStep(nextStep);

            if (stepCount >= stepRecords.size()) {
                stepRecords.add(stepRecord);

            } else {

                stepRecords.get(stepCount).setActuallyNextStep(nextStep);
                if (availableNextStep.containsAll(stepRecords.get(stepCount).getAvailableNextStep())) {
                    // 说明是回溯到这里的
                    deletePath(stepRecords, stepCount);
                    stepRecords.get(stepCount).setAvailableNextStep(availableNextStep);
                    stepRecords = stepRecords.subList(0, stepCount + 1);
                }
            }


            // 添加到路径中
            //path.add(nextStep);

            // 将该点在棋盘上记录为已经走的步数（回溯的时候，步骤要多减一）
            HorseChessBroad[nextStep.getColumn()][nextStep.getRow()] = stepCount;//assignStepCount == null ? stepCount : assignStepCount;

            System.out.println("通过回溯这次走：" + nextStep + "，已经走了" + (assignStepCount == null ? stepCount + 1 : assignStepCount + 1) + "步");

            // 打印棋盘
            printChessBroad();

            System.out.println("=======================================");

            // 继续走下一步
            go(nextStep/*, path*/, stepRecords, assignStepCount == null ? stepCount + 1 : assignStepCount + 1, null);
        } else {
            if (stepCount == HorseChessBroad.length * HorseChessBroad[0].length) {
                // 已经到了最后一步
                System.out.println("完成！！！");
                return;
            }

            // 调用回溯算法
            recall(stepRecords, assignStepCount == null ? stepCount : assignStepCount);
        }
    }

    private static void recall(List<StepRecord> stepRecords, Integer stepCount) {

        // 此路不通，回溯
        StepRecord prevStep = stepRecords.get(stepCount - 1);


        System.out.println("========================================================================");
        System.out.println("回溯：" + prevStep);

        // 上一步可用的步骤
        List<HorseChessLocation> prevAvailableNextStep = prevStep.getAvailableNextStep();

        // 上一步实际走的步骤
        HorseChessLocation actuallyNextStep = prevStep.getActuallyNextStep();

        //prevAvailableNextStep.remove(0); // 默认走的是可走下一步集合中的第一个

        // 过滤掉走不通的下一步

        List<HorseChessLocation> availableNextStepAfterRecall = filterForbiddenStep(prevStep);
        /*List<HorseChessLocation> availableNextStepAfterRecall = prevAvailableNextStep.stream().filter(location -> {

            return !(location.getRow() == actuallyNextStep.getRow() && location.getColumn() == actuallyNextStep.getColumn());

        }).collect(Collectors.toList());

        prevStep.setAvailableNextStep(availableNextStepAfterRecall);*/

        // 将上一步中，走不通的，但是又已经走了的路标记为没有走过
        deletePath(stepRecords, stepCount - 1);
        //HorseChessBroad[actuallyNextStep.getColumn()][actuallyNextStep.getRow()] = 0;

        if (availableNextStepAfterRecall.size() > 0) {

            HorseChessLocation chessLocation = availableNextStepAfterRecall.get(0);

            // 设置经过回溯之后要走的下一步
            prevStep.setActuallyNextStep(chessLocation);

            // 打印棋盘
            printChessBroad();


            System.out.println("回溯要走的下一步是：" + chessLocation);

            go(null/*, path*/, stepRecords, stepCount - 1, null);
        } else {
            System.out.println("==========================");
            System.out.println("进行二次回溯");
            // 上上次的记录
            StepRecord prev2Record = stepRecords.get(stepCount - 2);

            List<HorseChessLocation> prev2AvailableStepAfterRecall = filterForbiddenStep(prev2Record);

            prev2Record.setAvailableNextStep(prev2AvailableStepAfterRecall);

            // 上两步所走的 location 的列
            //Integer prev2Column = prev2Record.getActuallyNextStep().getColumn();

            // 上两步所走的 location 的行
            //Integer prev2Row = prev2Record.getActuallyNextStep().getRow();

            // 将做不通的路设置为 0
            //HorseChessBroad[prev2Column][prev2Row] = 0;

            deletePath(stepRecords, stepCount - 2);

            go(null, stepRecords, stepCount - 2, stepCount - 3);
        }

    }

    /**
     * 删除 StepRecordList 中指定位置
     */
    public static void deletePath(List<StepRecord> stepRecords, Integer fromIndex) {
        for (int i = fromIndex; i < stepRecords.size(); i++) {

            HorseChessLocation actuallyNextStep = stepRecords.get(i).getActuallyNextStep();

            // 所走的 location 的列
            Integer nextStepColumn = actuallyNextStep.getColumn();

            // 所走的 location 的行
            Integer nextStepRow = actuallyNextStep.getRow();

            // 将做不通的路设置为 0
            HorseChessBroad[nextStepColumn][nextStepRow] = 0;
        }
    }

    /**
     * 从 StepRecord 的 availableNextStep 中的找出 与 actuallyNextStep 相等的步骤，并将其删除，返回删除后可以走的步骤
     *
     * @param prevStep
     * @return
     */
    private static List<HorseChessLocation> filterForbiddenStep(StepRecord prevStep) {

        // 上一步可用的步骤
        List<HorseChessLocation> prevAvailableNextStep = prevStep.getAvailableNextStep();

        // 上一步实际走的步骤
        HorseChessLocation actuallyNextStep = prevStep.getActuallyNextStep();

        // 过滤掉走不通的下一步
        List<HorseChessLocation> availableNextStepAfterRecall = prevAvailableNextStep.stream().filter(location -> {

            return !(location.getRow() == actuallyNextStep.getRow() && location.getColumn() == actuallyNextStep.getColumn());

        }).collect(Collectors.toList());

        prevStep.setAvailableNextStep(availableNextStepAfterRecall);

        return availableNextStepAfterRecall;
    }

    public static void printChessBroad() {
        for (int i = 0; i < HorseChessBroad.length; i++) {
            for (int j = 0; j < HorseChessBroad[i].length; j++) {
                System.out.print(HorseChessBroad[j][i] + "\t");
            }
            System.out.println();
        }
    }

    /**
     * 根据当前位置解析出，下一步能走的位置
     *
     * @param horseChessLocation
     * @return
     */
    public static List<HorseChessLocation> availableNextStep(HorseChessLocation horseChessLocation) {

        List<HorseChessLocation> availableStep = new LinkedList<>();

        // 先右走两步
        int right2Step = horseChessLocation.getColumn() + 2;

        // 向右走一步
        int right1Step = horseChessLocation.getColumn() + 1;

        // 向上走一步
        int up1Step = horseChessLocation.getRow() - 1;

        // 向下走一步
        int down1Step = horseChessLocation.getRow() + 1;

        // 向上走两步
        int up2Step = horseChessLocation.getRow() - 2;

        // 向下走两步
        int down2Step = horseChessLocation.getRow() + 2;

        if (right2Step <= HorseChessBroad.length - 1) {
            // 可以向右踏（0、1、2、7）位置


            if (up1Step >= 0 && HorseChessBroad[right2Step][up1Step] == 0) {
                // 可以向上踏（0）


                availableStep.add(new HorseChessLocation(right2Step, up1Step));

            }


            if (down1Step <= HorseChessBroad[0].length - 1 && HorseChessBroad[right2Step][down1Step] == 0) {
                // 可以向下走

                availableStep.add(new HorseChessLocation(right2Step, down1Step));

            }
        }


        if (right1Step <= HorseChessBroad.length - 1) {


            if (up2Step >= 0 && HorseChessBroad[right1Step][up2Step] == 0) {

                availableStep.add(new HorseChessLocation(right1Step, up2Step));

            }


            if (down2Step <= HorseChessBroad[0].length - 1 && HorseChessBroad[right1Step][down2Step] == 0) {

                availableStep.add(new HorseChessLocation(right1Step, down2Step));
            }
        }

        // 先向左走两步
        int left2Step = horseChessLocation.getColumn() - 2;


        if (left2Step >= 0) {
            // 可以向右踏（0、1、2、7）位置

            if (up1Step >= 0 && HorseChessBroad[left2Step][up1Step] == 0) {
                // 可以向上踏（0）
                availableStep.add(new HorseChessLocation(left2Step, up1Step));
            }

            if (down1Step <= HorseChessBroad[0].length - 1 && HorseChessBroad[left2Step][down1Step] == 0) {
                // 可以向下走
                availableStep.add(new HorseChessLocation(left2Step, down1Step));
            }
        }

        // 向左走一步
        int left1Step = horseChessLocation.getColumn() - 1;
        if (left1Step >= 0) {


            if (up2Step >= 0 && HorseChessBroad[left1Step][up2Step] == 0) {
                availableStep.add(new HorseChessLocation(left1Step, up2Step));
            }

            if (down2Step <= HorseChessBroad[0].length - 1 && HorseChessBroad[left1Step][down2Step] == 0) {
                availableStep.add(new HorseChessLocation(left1Step, down2Step));
            }
        }

        return availableStep;
    }

    public static List<HorseChessLocation> availableNextStep2(HorseChessLocation horseChessLocation) {
        ArrayList<HorseChessLocation> availableStep = new ArrayList<>(8);

        // 先右走两步
        int right2Step = horseChessLocation.getColumn() + 2;

        // 向右走一步
        int right1Step = horseChessLocation.getColumn() + 1;

        // 向上走一步
        int up1Step = horseChessLocation.getRow() - 1;

        // 向下走一步
        int down1Step = horseChessLocation.getRow() + 1;

        // 向上走两步
        int up2Step = horseChessLocation.getRow() - 2;

        // 向下走两步
        int down2Step = horseChessLocation.getRow() + 2;

        // 先向左走两步
        int left2Step = horseChessLocation.getColumn() - 2;

        // 向左走一步
        int left1Step = horseChessLocation.getColumn() - 1;

        judgeAvailNextStepPublic(right2Step, up1Step, down1Step, availableStep);

        judgeAvailNextStepPublic(right1Step, up2Step, down2Step, availableStep);

        judgeAvailNextStepPublic(left2Step, up1Step, down1Step, availableStep);

        judgeAvailNextStepPublic(left1Step, up2Step, down2Step, availableStep);


        return availableStep;
    }

    private static void judgeAvailNextStepPublic(int column, int prevRow, int nextRow, ArrayList<HorseChessLocation> availableStep) {
        if (column >= 0) {


            if (prevRow >= 0 && HorseChessBroad[column][prevRow] == 0) {
                availableStep.add(new HorseChessLocation(column, prevRow));
            }

            if (nextRow <= HorseChessBroad[0].length - 1 && HorseChessBroad[column][nextRow] == 0) {
                availableStep.add(new HorseChessLocation(column, nextRow));
            }
        }
    }
}
